Gradient Tree Boosting Algorithm

在机器学习各大算法中,决策树这种算法有着很多良好的特性,其现有的特点就有训练的时间复杂度$Omega$较低,对新样本预测的过程比较快,同时模型容易展示(容易将得到的决策树做成图片展示出来)等。但与此同时,单决策树又有一些不好的地方,比如说容易over-fitting。虽然目前有一些方法,比如剪枝可以减少这种over-fitting的程度,但结果还是不太理想。

与决策树相关的ensemble model(比如说有Boosting,Bagging等)算法比较多,比如RandomForest、Adaboost、GBRT等,这些算法最终的结果是生成$N$($N$的取值有可能成百上千)棵树,这样得到的最终模型可以大大减少单个决策树带来的缺陷。换言之,集成算法有点类似于“三个臭皮匠赛过一个诸葛亮”的做法。虽然这几百棵决策树中的每一棵都很简单(相对于C4.5这种单决策树而言),但将他们组合起来之后就能达到非常不错的模型。另外,值得注意的是,虽然这些算法都是由决策树演变而来,但不同的集成模型在训练的细节上伴有一些差异,在文章后面会对这些算法做一个本质的对比。下面先来讲解下本文的核心内容——Gradient Tree Boosting。

Introduction to Gradient Tree Boosting

Gradient Tree Boosting 算法最初是FreidMan在2000年提出来的,是一种集成算法(或是组合算法)。该算法的名字可以说是千奇百态,有叫GBRT(gradient boosting regression tree),也有说成GBM、GBDT的。它的base learners是决策树,既可以用来训练regression model,也可以用做classification。在分类性能上,能够和random forest媲美,甚至在有的dataset上表现的有过之而无不及。如今,Gradient Tree Boosting模型还广泛地运用在Web搜索排行榜以及生态学上,所以值得我们去花点时间认真学习。根据scikit-learn官网的介绍,GTB的优势有以下三大点:

  • 自然而然地处理混合类型的数据;
  • 预测能力强;
  • 在输出空间对于异常值的鲁棒性强(通过强大的损失函数)。

然而,也存在一些劣势:

  • 可扩展性方面,由于提升的时序性,不能进行并行处理。

尽管如此,由于gradient tree boosting algorithm的表现性能很好,所以受到广大业界人士的青睐。下面来介绍下梯度提升树的算法原理。

算法原理

gradient tree boosting 算法的核心在于,它的每棵树都是从上一次训练的所有树的残差中进行学习,进而拟合一棵回归(分类)树。
。在训练的时候,残差近似等于当前模型中损失函数的负梯度值,公式如下:

gradient boosting是boosting算法的一种,也可以说是Boosting算法的一种改进,原始的Boosting算法(Adaboost)是:在算法初始化阶段,为每一个样本赋予一个相等的weight,换言之,每个样本在开始都是一样重要的。接下来,每一次训练后得到的模型,对数据点的估计会有所差异,所以在每一步结束后,我们需要对weight进行处理,而处理的方式就是通过增加错分类的样本点的weight,同时减少分类正确的样本点的weight。这样能够确保,如果某些点经常被分错,那么就会被“严重关注”,也就会被赋予一个很高的weight。然后等进行了$N$次迭代(迭代次数由用户指定),将会得到$N$个简单的base learner,最后将它们组合起来,可以对它们进行加权(错误率越大的base learner 其权重值越小,错误率越小的基分类器权重值越大)、或者让它们进行投票等得到一个最终的模型。

gradient boosting与传统的boosting有着很大的区别,它的每一次计算都是为了减少上一次的 residual,而为了减少这些residual,它会在residual减少的gradient方向上建立一个新的 model。所以说,在gradient boosting algorithm中,新model建立的目的是为了使先前模型的残差往梯度方向减少,与传统的boosting算法对正错样本赋予不同加权的做法有着极大的区别。

gtb算法理论的核心包括三大点:

  1. regression tree
  2. gradient descent
  3. boosting - Shrinkage

gradient tree boosting algorithm - Regression

对于给定的输入:训练数据集 $T={(x_1,y_1),(x_2,y_2),…,(x_n,y_n)},损失函数$L(y,f(x))$;
输出结果:一棵回归树$\tilde{f}(x)$

(1)首先初始化

$$f_0(x)=\arg \ \min_c \sum_{i=1}^{N}L(y_i, c)$$

建立一个model,估计一个使loss function 极小化的常数值,此时的model是一个只有一个节点的树;

(2)迭代的建立M棵boosting tree

$for m=1 to M:$(第一层循环开始)
$for i=1 to N:$(第二层循环1) 计算loss function 的negative gradient在当前model的值,并将它作为residual的估计值。

接着,对于$r_{mi}$拟合一棵回归树,得到第$m$棵树的叶节点区域 $c_{mj} ,j=1,2,…,J$

$for j=1 to J:$(第二层循环2),计算:

利用线性搜索估计叶节点区域的值,使损失函数极小化;

然后,更新

(3)最后得到的$f_{m}(x)$就是我们最终的模型

从式子中可以看出,gradient tree boosting algorithm 本质上是一个加和模型,并在推导中结合了前向分步算法。


scikit-learn中的GTB

在scikit-learn中对GTB算法有了很好的封装,对于分类可以选择的损失函数有逻辑回归和指数函数,对于回归的损失函数相对比较多,有最小二乘法、最小绝对偏差函数、huber以及分位数等。

下面是sklearn中的一个分类原例:

1
2
3
4
5
6
7
8
9
>>> from sklearn.datasets import make_hastie_10_2
>>> from sklearn.ensemble import GradientBoostingClassifier
>>> X, y = make_hastie_10_2(random_state=0)
>>> X_train, X_test = X[:2000], X[2000:]
>>> y_train, y_test = y[:2000], y[2000:]
>>> clf = GradientBoostingClassifier(n_estimators=100, learning_rate=1.0,
... max_depth=1, random_state=0).fit(X_train, y_train)
>>> clf.score(X_test, y_test)
0.913...

其中$n_estimators$表示弱分类器的个数,$learning_rate$表示学习率,$max_depth$表示树的最大深度等。GTB的参数比较多,在实际应用中需要自己去调整合适的参数。

A comparison of ensemble algorithms

基于决策树的组合算法常用的有三个,分别是Adaboost、RandomFrest以及本文的GBRT。

Adaboost是通过迭代的学习每一个基分类器,每次迭代中,把上一次错分类的数据权值增大,正确分类的数据权值减小,然后将基分类器的线性组合作为一个强分类器,同时给分类误差率较小的基本分类器以大的权值,给分类误差率较大的基分类器以小的权重值。Adaboost使用的是自适应的方法,其中概率分布式变化的,关注的是难分类的样本。详细内容请参考之前的文章:机器学习算法-Adaboost

Random Forest与adaboost有些区别,可以说一种改进的bagging算法。Random Forest不仅对样本进行sampling,还对feature进行sampling。它通过随机的方式建立一个森林,森林里面有许多棵决策树,并且每一棵树之间是没有联系的。在得到森林之后,当有一个新的input sample进来的时候,就让森林中的每一棵决策树分别对其进行判断,看这个样本应该属于哪一类(就分类算法而言),然后看看哪一类选择最多(随机森林使用到的是 vote方式),就预测这个样本为该class。在建立每一棵决策树的过程中,有两点需要注意,即采样完全分裂。首先是两个随机采样的过程,random forest对输入的数据要进行采样列采样。对于行采样,是采用有放回的方式,即bootstrap sampling,也就是在采样得到的样本集合中,可能有重复的样本。举个例子,假设输入样本为$N$个,那么采样的样本也为$N$个。这样使得在训练的时候,每一棵树的输入样本都不是全部的样本,从某种程度上讲,相对不容易出现over-fitting。其次就是列采样,这个过程是从$M$个feature中,选择$m$个($m << M$)。之后就是对采样之后的数据使用完全分裂的方式建立决策树模型。最后得到的决策树,它的某一个叶子节点要么是无法继续分裂的,要么里面的所有样本的都是指向的同一类别。一般很多的决策树算法都一个重要的步骤-Pruning(剪枝),但是random forest并不这样干,由于之前的两个随机采样的过程保证了样本的随机性,所以替代了Pruning这个工作,也不太容易出现over-fitting。按照这种算法得到的random forest中的每一棵决策树都是非常弱的,但是当你把它们组合在一起的时候,就得对它刮目相看了。random forest可以这样来形容:每一棵决策树就是一个精通于某一领域的专家(因为我们从$M$个feature set中选择$m$个sub set让每一棵决策树进行学习),这样在random forest中就有了很多个精通不同领域的专家,对一个新的问题(input data),可以用不同的角度去看待它,最终由各个专家投票得到结果。random forest的分类准确率可以与adaboost媲美,但它对noise data更加鲁棒,运行速度比adaboost也快得多。

另外,random forest是可以实现并行化的,而adaboost无法并行。同时,random forest等bagging算法其本质是降variance的,而adaboost等boosting算法其实降的是bias。

最后,对于gradient tree boosting algorithm,它的每一次计算都是为了减少上一次训练模型的residual,而为了减少这些残差,可以在残差减少的梯度(Gradient)方向上建立一个新模型。这与adaboost和随机森林还是有很大区别的。

References